from typing import *


class Solution:
    def maxScore(
        self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]
    ) -> int:

        dp = [[0] * n for _ in range(k + 1)]
        ans = 0
        # def max(a, b):
        #     return a if a >= b else b

        for i in range(k):
            for j in range(n):
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + stayScore[i][j])
                for t in range(n):
                    dp[i + 1][t] = max(dp[i + 1][t], dp[i][j] + travelScore[j][t])
                    ans = max(ans, dp[i + 1][t])
        return ans
